//请你设计一个用于存储字符串计数的数据结构，并能够返回计数最小和最大的字符串。 
//
// 实现 AllOne 类： 
//
// 
// AllOne() 初始化数据结构的对象。 
// inc(String key) 字符串 key 的计数增加 1 。如果数据结构中尚不存在 key ，那么插入计数为 1 的 key 。 
// dec(String key) 字符串 key 的计数减少 1 。如果 key 的计数在减少后为 0 ，那么需要将这个 key 从数据结构中删除。测试用例
//保证：在减少计数前，key 存在于数据结构中。 
// getMaxKey() 返回任意一个计数最大的字符串。如果没有元素存在，返回一个空字符串 "" 。 
// getMinKey() 返回任意一个计数最小的字符串。如果没有元素存在，返回一个空字符串 "" 。 
// 
//
// 
//
// 示例： 
//
// 
//输入
//["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", 
//"getMinKey"]
//[[], ["hello"], ["hello"], [], [], ["leet"], [], []]
//输出
//[null, null, null, "hello", "hello", null, "hello", "leet"]
//
//解释
//AllOne allOne = new AllOne();
//allOne.inc("hello");
//allOne.inc("hello");
//allOne.getMaxKey(); // 返回 "hello"
//allOne.getMinKey(); // 返回 "hello"
//allOne.inc("leet");
//allOne.getMaxKey(); // 返回 "hello"
//allOne.getMinKey(); // 返回 "leet"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= key.length <= 10 
// key 由小写英文字母组成 
// 测试用例保证：在每次调用 dec 时，数据结构中总存在 key 
// 最多调用 inc、dec、getMaxKey 和 getMinKey 方法 5 * 10⁴ 次 
// 
// Related Topics 设计 哈希表 链表 双向链表 👍 222 👎 0

package com.cute.leetcode.editor.cn;

import java.util.*;

public class AllOoneDataStructure {
    public static void main(String[] args) {
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class AllOne {
        class Node{// 创建节点类，节点为双向链表中的节点
            int cnt;// cnt为key出现次数
            Set<String> set = new HashSet<>();// 保存出现次数为cnt的所有key
            Node left,right;
            Node(int cnt){
                this.cnt = cnt;
            }
        }
        Node hh, tt;//头尾虚拟节点
        Map<String, Node> map = new HashMap<>();// 根据key保存Node

        public AllOne() {
            hh = new Node(-1000);
            tt = new Node(-1000);
            hh.right = tt;
            tt.left = hh;
        }
        private void clear(Node node){
            if (node.set.size() == 0){// 如果set为空，从双向链表中删除当前节点
                node.left.right = node.right;
                node.right.left = node.left;
            }
        }
        public void inc(String key) {
            if (map.containsKey(key)){
                Node node = map.get(key);// 拿到当前key对应的节点
                node.set.remove(key);// 当前节点先删除key
                int cnt = node.cnt;
                Node next;
                if (node.right.cnt == cnt + 1) next = node.right;// 下一个长度存在
                else {
                    next = new Node(cnt + 1);//下一个长度不存在时新建节点并入队列
                    next.right = node.right;
                    next.left = node;
                    node.right.left = next;
                    node.right = next;
                }
                next.set.add(key);// 向新节点添加key
                map.put(key, next);// 当前key存到了新节点
                clear(node);// 尝试删除之前的节点
            }else {// 当前key不存在于链表中
                Node node;
                if (hh.right.cnt == 1) node = hh.right;// 存在出现次数为1的节点
                else {// 不存在出现次数为1的节点
                    node = new Node(1);
                    node.right = hh.right;
                    node.left = hh;
                    hh.right.left = node;
                    hh.right = node;
                }
                node.set.add(key);
                map.put(key, node);
            }
        }

        public void dec(String key) {// 此时题目保证key一定出现过
            Node node = map.get(key);
            node.set.remove(key);
            int cnt = node.cnt;
            if (cnt == 1) map.remove(key);// 直接删没了
            else {
                Node prev;
                if (node.left.cnt == cnt - 1) prev = node.left;
                else {
                    prev = new Node(cnt - 1);
                    prev.right = node;
                    prev.left = node.left;
                    node.left.right = prev;
                    node.left = prev;
                }
                prev.set.add(key);
                map.put(key, prev);
            }
            clear(node);// 尝试删除节点
        }

        public String getMaxKey() {
            Node node = tt.left;// 尾节点的左边就是最小大值
            for (String s : node.set) return s;
            return "";
        }

        public String getMinKey() {
            Node node = hh.right;// 首节点的右边第一个就是最小值
            for (String s : node.set) return s;
            return "";
        }
    }

/**
 * Your AllOne object will be instantiated and called as such:
 * AllOne obj = new AllOne();
 * obj.inc(key);
 * obj.dec(key);
 * String param_3 = obj.getMaxKey();
 * String param_4 = obj.getMinKey();
 */
//leetcode submit region end(Prohibit modification and deletion)

}